﻿#define _CRT_SECURE_NO_WARNINGS 
//复习链表经典面试题

//1.移除链表元素
// 
// 创建新链表;
//typedef struct ListNode ListNode;
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
//    dummy->next = NULL;
//    ListNode* pcur = head, * newtail = dummy;
//    while (pcur)
//    {
//        if (pcur->val != val)
//        {
//            //尾插;
//            newtail->next = pcur;
//            newtail = newtail->next;
//        }
//        pcur = pcur->next;
//    }
//    newtail->next = NULL;
//    ListNode* ret = dummy->next;
//    free(dummy);
//    dummy = NULL;
//    return ret;
//}
/////////法二：遍历原链表，删除节点
//typedef struct ListNode ListNode;
//struct ListNode* removeElements(struct ListNode* head, int val)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* pcur = head, * prev = head;
//    ListNode* del = NULL;
//    while (pcur)
//    {
//        if (pcur->val == val)
//        {
//            if (pcur == head)
//            {
//                del = head;
//                prev = prev->next;
//                pcur = pcur->next;
//                head = head->next;
//                free(del);
//                del = NULL;
//            }
//            //不是头结点;
//            else
//            {
//                del = pcur;
//                pcur = pcur->next;
//                prev->next = pcur;
//                free(del);
//                del = NULL;
//            }
//        }
//        else
//        {
//            prev = pcur;
//            pcur = pcur->next;
//        }
//    }
//    return head;
//}

//2.反转链表
// 
//创建新链表;
//typedef struct ListNode ListNode;
//struct ListNode* reverseList(struct ListNode* head)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
//    dummy->next = NULL;
//    ListNode* ptail = dummy;
//    while (head)
//    {
//        //头插;
//        ptail = dummy->next;
//        ListNode* next = head->next;
//        head->next = ptail;
//        dummy->next = head;
//        head = next;
//    }
//    return dummy->next;
//}

//三指针反转链表;
//typedef struct ListNode ListNode;
//struct ListNode* reverseList(struct ListNode* head)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* p1 = NULL, * p2 = head, * p3 = head->next;
//    while (p2)
//    {
//        p2->next = p1;
//        p1 = p2;
//        p2 = p3;
//        if (p3)
//            p3 = p3->next;
//    }
//    return p1;
//}

//3.链表中间节点;
//typedef struct ListNode ListNode;
//struct ListNode* middleNode(struct ListNode* head)
//{
//    ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    return slow;
//}

//4.输出该链表中倒数第k个结点
//typedef struct ListNode ListNode;
//int kthToLast(struct ListNode* head, int k)
//{
//    ListNode* fast = head, * slow = head;
//    while (k)
//    {
//        fast = fast->next;
//        k--;
//    }
//    while (fast)
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//    return slow->val;
//}

//5.合并两个升序链表;
//typedef struct ListNode ListNode;
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//    if (list1 == NULL)
//        return list2;
//    if (list2 == NULL)
//        return list1;
//    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
//    dummy->next = NULL;
//    ListNode* ptail = dummy;
//    while (list1 && list2)
//    {
//        if (list1->val <= list2->val)
//        {
//            //尾插;
//            ptail->next = list1;
//            ptail = ptail->next;
//            list1 = list1->next;
//        }
//        else
//        {
//            ptail->next = list2;
//            ptail = ptail->next;
//            list2 = list2->next;
//        }
//    }
//    if (list1)
//        ptail->next = list1;
//    else
//        ptail->next = list2;
//    return dummy->next;
//}
/////////6.分割链表;
//typedef struct ListNode ListNode;
//struct ListNode* partition(struct ListNode* head, int x)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* dummySmall = (ListNode*)malloc(sizeof(ListNode));
//    ListNode* dummyBig = (ListNode*)malloc(sizeof(ListNode));
//    dummyBig->next = dummySmall->next = NULL;
//    ListNode* pcur = head;
//    ListNode* ptails = dummySmall, * ptailb = dummyBig;
//    while (pcur)
//    {
//        if (pcur->val < x)
//        {
//            //尾插到小链表中;
//            ptails->next = pcur;
//            ptails = ptails->next;
//        }
//        else
//        {
//            //尾插到大链表中;
//            ptailb->next = pcur;
//            ptailb = ptailb->next;
//        }
//        pcur = pcur->next;
//    }
//    //连接小大链表;
//    ptailb->next = NULL;
//    ptails->next = dummyBig->next;
//    return dummySmall->next;
//}
// 
//7.链表的回文结构
//typedef struct ListNode ListNode;
//ListNode* middle(ListNode* head)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    return slow;
//}
//ListNode* roundList(ListNode* head)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
//    dummy->next = NULL;
//    ListNode* pcur = head;
//    while (pcur)
//    {
//        ListNode* next = pcur->next;
//        //头插;
//        pcur->next = dummy->next;
//        dummy->next = pcur;
//        pcur = next;
//    }
//    return dummy->next;
//}
//class PalindromeList {
//public:
//    bool chkPalindrome(ListNode* A)
//    {
//        // write code here
//        ListNode* mid = middle(A);
//        ListNode* newhead = roundList(mid);
//        ListNode* pcur = A;
//        while (newhead)
//        {
//            if (newhead->val != pcur->val)
//                return false;
//            newhead = newhead->next;
//            pcur = pcur->next;
//        }
//        return true;
//    }
//};


//8.输入两个链表，找出它们的第一个公共结点
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    int m = 1, n = 1;
//    struct ListNode* curA = headA;
//    struct ListNode* curB = headB;
//    while (curA->next)
//    {
//        curA = curA->next;
//        m++;
//    }
//    while (curB->next)
//    {
//        curB = curB->next;
//        n++;
//    }
//    if (curA != curB)
//        return NULL;
//    int gap = abs(m - n);
//    struct ListNode* fast = headA;
//    struct ListNode* slow = headB;
//    if (m < n)
//    {
//        fast = headB;
//        slow = headA;
//    }
//    while (gap--)
//    {
//        fast = fast->next;
//    }
//    while (fast != slow)
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//    return slow;
//}

//9.给定一个链表，判断链表中是否有环
//typedef struct ListNode ListNode;
//bool hasCycle(struct ListNode* head)
//{
//    if (head == NULL)
//        return false;
//    ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//            return true;
//    }
//    return false;
//}

//10.给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL 
//typedef struct ListNode ListNode;
//struct ListNode* detectCycle(struct ListNode* head)
//{
//    if (head == NULL)
//        return NULL;
//    ListNode* slow = head, * fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        if (fast == slow)
//        {
//            ListNode* meet = slow;
//            while (head != meet)
//            {
//                meet = meet->next;
//                head = head->next;
//            }
//            return meet;
//        }
//    }
//    return NULL;
//}


//11.链表深拷贝;
//typedef struct Node Node;
//struct Node* copyRandomList(struct Node* head)
//{
//    if (head == NULL)
//        return NULL;
//    Node* cur = head;
//    while (cur)
//    {
//        Node* copy = (Node*)malloc(sizeof(Node));
//        copy->next = cur->next;
//        cur->next = copy;
//        copy->val = cur->val;
//        cur = copy->next;
//    }
//    //random
//    cur = head;
//    while (cur)
//    {
//        Node* copy = cur->next;
//        Node* next = copy->next;
//        if (cur->random == NULL)
//            copy->random = NULL;
//        else
//            copy->random = cur->random->next;
//        cur = next;
//    }
//    //拿下链表进行尾插
//    cur = head;
//    Node* dummy = (Node*)malloc(sizeof(Node));
//    Node* newtail = dummy;
//    while (cur)
//    {
//        Node* newnode = cur->next;
//        newtail->next = newnode;
//        newtail = newtail->next;
//        cur = newnode->next;
//    }
//    return dummy->next;
//}